package org.example.graph_theory;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.PriorityQueue;

public class Minimum_cost_to_connect_all_points {
    public static void main(String[] args) {
        //连接所有点的最小费用

//        给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
//        连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
//        请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
        int[][] points = {{3, 12}, {-2, 5}, {-4, 1}};
//        int[][] points = {{-1000000,-1000000},{1000000,1000000}};
//        int[][] points = {{2,-3},{-17,-8},{13,8},{-17,-15}};
        int i = minCostConnectPoints(points);
        System.out.println(i);
    }

    //kruskal算法，在加上并查集理论，再加上优先级队列,87ms
    public static int minCostConnectPoints(int[][] points) {
        if (points.length==1) return 0;
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        int[] father = new int[points.length];

        for (int i = 0; i < points.length; i++) {
            father[i] = i;
            for (int j = i + 1; j < points.length; j++) {
                int len = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                priorityQueue.offer(new int[]{i, j, len});
            }
        }

        int totallen = 0;
        int len = 0;
        while (len < points.length-1) {
            int[] edges = priorityQueue.poll();
            int s = edges[0], d = edges[1], weight = edges[2];

            int roots = find(s,father);
            int rootd = find(d,father);

            if (roots==rootd) continue;
            father[rootd] = roots;

            totallen+=weight;
            len++;

        }

        return totallen;
    }

    public static int find(int node,int[] father){
        if (father[node] != node){
            father[node] = find(father[node],father);
        }
        return father[node];
    }

    //prim算法优化后127ms，时间复杂度为O(n**2logn)
    public static int minCostConnectPoints3(int[][] points) {

        //主要使用优先级队列自动排序，算法时间复杂度为O(logn)
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[2] - b[2]);

        for (int i = 1; i < points.length; i++) {
            int len = Math.abs(points[0][0] - points[i][0]) + Math.abs(points[0][1] - points[i][1]);
            priorityQueue.offer(new int[]{0, i, len});
        }

        HashSet<Integer> visited = new HashSet<>();
        visited.add(0);

        int totalLen = 0;
        while (visited.size() < points.length) {
            int[] edges = priorityQueue.poll();
            int from = edges[0], to = edges[1], weight = edges[2];

            if (visited.contains(to)) continue;
            visited.add(to);
            totalLen += weight;

            for (int i = 0; i < points.length; i++) {
                if (visited.contains(i)) continue;
                int len = Math.abs(points[to][0] - points[i][0]) + Math.abs(points[to][1] - points[i][1]);
                priorityQueue.offer(new int[]{to, i, len});
            }
        }

        return totalLen;
    }

    //prim算法超时，时间复杂度O(n**3)
    public static int minCostConnectPoints2(int[][] points) {

        int[][] pl = new int[points.length][points.length];
        HashSet<Integer> visited = new HashSet<>();
        visited.add(0);

        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                pl[i][j] = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
            }
        }

        int totallen = 0;

        while (visited.size() < points.length) {
            int node = -1;
            int minlen = Integer.MAX_VALUE;
            for (Integer index : visited) {
                for (int i = 0; i < points.length; i++) {
                    if (visited.contains(i)) continue;
                    if (minlen > pl[index][i]) {
                        minlen = pl[index][i];
                        node = i;
                    }
                }
            }
            totallen += minlen;
            visited.add(node);
        }


        return totallen;
    }
}
